#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle.empty()) {
            return 0;
        }
        return kmp(haystack, needle);   
    }

private:
    // 构建 next 数组 (LPS 数组)
    void computeNext(const string& needle, vector<int>& next) {
        int n = needle.length();
        next.assign(n, 0);
        int length = 0; // 当前最长公共前后缀的长度
        int i = 1;
        while (i < n) {
            if (needle[i] == needle[length]) {
                length++;
                next[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = next[length - 1];
                } else {
                    next[i] = 0;
                    i++;
                }
            }
        }
    }

    int kmp(const string& haystack, const string& needle) {
        int n = haystack.length();
        int m = needle.length();
        if (m == 0) return 0;
        if (n < m) return -1;

        vector<int> next(m);
        computeNext(needle, next);

        int i = 0; // haystack 的指针
        int j = 0; // needle 的指针
        while (i < n) {
            if (needle[j] == haystack[i]) {
                i++;
                j++;
            }
            if (j == m) {
                return i - j; // 找到匹配，返回起始索引
            } else if (i < n && needle[j] != haystack[i]) {
                if (j != 0) {
                    j = next[j - 1];
                } else {
                    i++;
                }
            }
        }
        return -1;
    }
};